public class test {
    //蓝桥杯 Dijkstra求最短路
    public class Main {
        public static int n;
        public static int m;
        public static int[] dis;
        public static boolean[] count;
        public static List<int[]>[] list;
        public static int INF = 0x3f3f3f3f;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            n = in.nextInt();
            m = in.nextInt();
            //存储从1到x间的最短路径
            dis = new int[n + 1];
            count = new boolean[n + 1];
            list = new ArrayList[n + 1];
            for(int i = 1;i <= n;i++){
                list[i] = new ArrayList<>();
            }
            for(int i = 1;i <= m;i++){
                int a = in.nextInt();
                int b = in.nextInt();
                int c = in.nextInt();
                list[a].add(new int[]{b,c});
                //list[b].add(new int[]{a,c});
            }
            dijkstra();
            System.out.println(dis[n] == INF ? -1 : dis[n]);
        }
        public static void dijkstra(){
            //代表能到达的节点,以及两点间距离
            Arrays.fill(dis,INF);
            dis[1] = 0;
            PriorityQueue<int[]> p = new PriorityQueue<>(Comparator.comparing(k -> k[1]));
            p.add(new int[]{1,0});
            while(!p.isEmpty()){
                int[] t = p.poll();
                if(count[t[0]]) continue;
                count[t[0]] = true;
                for(int[] arr : list[t[0]]){
                    int v = arr[0];
                    int w = arr[1];
                    if(dis[v] > dis[t[0]] + w){
                        dis[v] = dis[t[0]] + w;
                        p.add(new int[]{v,dis[v]});
                    }
                }
            }
        }
    }
    //蓝桥杯 电动车(⭐⭐⭐⭐)
    public class Main {
        public static int n;
        public static int m;
        public static int[] dis;
        public static boolean[] count;
        //代表从 i 到 x 路途中的最大路距
        public static List<int[]>[] list;
        public static int INF = 0x3f3f3f3f;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            n = in.nextInt();
            m = in.nextInt();
            dis = new int[n + 1];
            count = new boolean[n + 1];
            list = new List[n + 1];
            for(int i = 1;i <= n;i++){
                list[i] = new ArrayList<>();
            }
            for(int j = 1;j <= m;j++){
                int a = in.nextInt();
                int b = in.nextInt();
                int c = in.nextInt();
                list[a].add(new int[]{b,c});
                list[b].add(new int[]{a,c});
            }
            dijkstra(1);
            int max = 0;
            for(int i = 1;i <= n;i++){
                if(dis[i] == INF){
                    System.out.println(-1);
                    return;
                }else {
                    max = Math.max(max,dis[i]);
                }
            }
            System.out.println(max);
        }
        public static void dijkstra(int n){
            PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparing(q -> q[1]));
            Arrays.fill(dis,INF);
            queue.add(new int[]{1,0});
            dis[1] = 0;
            while(!queue.isEmpty()){
                int[] t = queue.poll();
                int index = t[0];
                if(count[index]) continue;
                count[index] = true;
                List<int[]> path = list[index];
                for (int[] a: path) {
                    int v = a[0];
                    int w = a[1];
                    int max = Math.max(dis[index],w);
                    if(dis[v] > max){
                        dis[v] = max;
                    }
                    queue.add(new int[]{v,dis[v]});
                }
            }
        }
    }
    //蓝桥杯 蓝桥公园(⭐⭐⭐)
    public class Main {
        public static long INF = 0x3f3f3f3f3f3f3f3fl - 100;
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            int m = in.nextInt();
            int q = in.nextInt();
            long[][] dp = new long[n + 1][n + 1];
            for(int i = 1;i <= n;i++){
                Arrays.fill(dp[i],INF);
                dp[i][i] = 0;
            }
            for(int i = 1;i <= m;i++){
                int u = in.nextInt();
                int v = in.nextInt();
                long w = in.nextLong();
                dp[u][v] = Math.min(dp[u][v],w);
                dp[v][u] = Math.min(dp[v][u],w);
            }
            for(int k = 1;k <= n;k++){
                for(int j = 1;j <= n;j++){
                    for(int i = 1;i <= n;i++){
                        if(dp[i][k] != INF && dp[k][j] != INF)
                            dp[i][j] = Math.min(dp[i][j],dp[i][k] + dp[k][j]);
                    }
                }
            }
            while(q-- > 0){
                int start = in.nextInt();
                int end = in.nextInt();
                System.out.println(dp[start][end] == INF ? -1 : dp[start][end]);
            }
        }
    }
}
